class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    /*
    对于矩阵中某一点，我们可以沿上下左右四个方向（边界情况除外）前进，
    在前进之后如果所在点的值小于等于上一点的值，
    那么说明此路径无效，返回上一点，并选取其他路径进行尝试。
    已经知道以该点为头的最长递增路径长度，
    那么在dfs查找时可以直接使用这个长度，
    而无需再次计算，所以我们可以用一个矩阵vis将已经计算得到的最长递增路径
    */
    int solve(vector<vector<int> >& matrix) {
        // write code here
      int m=matrix.size();
      int n=matrix[0].size();
        if(m<1)
            return 0;
       vector<vector<int>>vis(m,vector<int>(n,0));
        int res=INT_MIN;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                res=max(res,dfs(matrix,i,j,INT_MIN,vis));
            }
        }
        return res;
    }
     int dfs(vector<vector<int>>&matrix,int x,int y,int value,vector<vector<int>>&vis)
     {
         if(x>=matrix.size()||x<0||y>=matrix[0].size()||y<0)
             return 0;
         if(matrix[x][y]<=value)
             return 0;
         if(vis[x][y]!=0)
             return vis[x][y];
         vis[x][y]++;
         int up=dfs(matrix,x-1,y,matrix[x][y],vis);
         int down=dfs(matrix, x+1, y, matrix[x][y],vis);
         int left=dfs(matrix,x,y-1,matrix[x][y],vis);
         int right=dfs(matrix,x,y+1,matrix[x][y],vis);
         vis[x][y]=max(vis[x][y],max(max(up,down),max(left,right))+1);
         return vis[x][y];
        }
};